from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * 2 for _ in range(len(prices))]
        # 0 代表不持有
        dp[0][1] = -prices[0]
        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0])
            dp[i][1] = max(- prices[i], dp[i - 1][1])
        return dp[-1][0]


if __name__ == '__main__':
    s = Solution()
    r = s.maxProfit([7, 1, 5, 3, 6, 4])
    print(r)
